/*
 *  Main.cpp
 *  Created on: 2014年5月6日
 *  Author: rock
 */
#include <iostream>
#include "common.h"
#include "Sort.h"
#include "HeapSort.h"
#include "TreeNode.h"
#include "KBigNum.h"
#include "BinarySortTree.h"
#include "BinTree.h"
#include "Link.h"
#include "MaxAscSeq.h"
#include "Graph.h"
#include "FindWay.h"
#include "Composite.h"
#include "BinarySearch.h"
#include "StringContain.h"
#include "Stack.h"

using namespace std;

void outPutResults(int * arrayPtr, int LEN );

void initData(int *arrayPtr)
{
	arrayPtr[0] = 60;
	arrayPtr[1] = 15;
	arrayPtr[2] = 337;
	arrayPtr[3] = 89;
	arrayPtr[4] = 67;
	arrayPtr[5] = 39;
	arrayPtr[6] = 14;
	arrayPtr[7] = 38;
	arrayPtr[8] = 1324;
	arrayPtr[9] = 769;

	outPutResults(arrayPtr, 10);
}

void outPutResults(int * arrayPtr, int LEN )
{
	cout << "Before sort:" << endl;
	for (int i = 0; i < LEN; i++)
		cout << arrayPtr[i] << " ";

	cout << endl;
}

void CalculateSort()
{
	/*计数排序测试 C plus plus*/
	string cppNoOrder = "SDFLJWOJFLXCMVLSDJFLWLSDJFLSDFJLWEJFLSJDL";
	string cppHelper = cppNoOrder;
	CounterSort(cppNoOrder, cppHelper);
	cout << cppHelper << endl;


	/*计数排序测试 C lang*/
	const char * noOrder = "ASSAFSKFDFBLERJGERJGERGLDFGJDFLBLDFGJELRE";
	char *help = new char[(strlen(noOrder)+1)*sizeof(char)];
	CounterSort(noOrder, help);
	cout << help << endl;

	delete[] help;

}

void SortTest()
{
	const int LEN = 10;
	int * arrayPtr = new int[10];

	initData(arrayPtr);
	selectSort(arrayPtr, LEN);
	outPutResults(arrayPtr, LEN);
	cout << endl;

	initData(arrayPtr);
	insertSort(arrayPtr, LEN);
	outPutResults(arrayPtr, LEN);
	cout << endl;

	initData(arrayPtr);
	bubleSort(arrayPtr, LEN);
	outPutResults(arrayPtr, LEN);
	cout << endl;

	initData(arrayPtr);
	quickSort(arrayPtr, 0, LEN - 1);
	outPutResults(arrayPtr, LEN);
	cout << endl;

	/*计数排序测试*/
	CalculateSort();

	cout << endl;
}


void BinarySortTreeTest()
{
	BinarySortTree * tree = new BinarySortTree();
	tree->Add(3);
	tree->Add(32);
	tree->Add(23);
	tree->Add(90);
	tree->Add(13);
	tree->Add(2);
	tree->Add(342);
	tree->Add(57);
	tree->Add(38);
	tree->Add(77);
	tree->Add(46);
	tree->Add(88);
	tree->Add(238);
	tree->Add(34);

	tree->Print();
	cout << endl;
	tree->Delete(13);
	tree->Delete(88);
	tree->Delete(57);
	tree->Add(66);
	tree->Add(99);

	tree->Print();
	cout << endl;
}

void TreeSort()
{
	TreeNode * root = BuildBinaryTree();
	int depth = CalcTreeDepth(root);
	cout << endl << "Tree depth is " << depth << endl;
	/*
	cout << endl << "-----------------------------------------------------------------------------"<<endl;
	cout << endl << "PreOrder -----------------------" << endl;
	PreOrderTree(root);
	cout << endl << "PreOrder -----------------------" << endl;
	PreOrderTreeIterater(root);


	cout << endl << "-----------------------------------------------------------------------------"<<endl;
	cout << endl << "MidOrder -----------------------" << endl;
	MidOrderTree(root);
	cout << endl << "MidOrder -----------------------" << endl;
	MidOrderTreeIterater(root);


	cout << endl << "-----------------------------------------------------------------------------"<<endl;
	cout << endl << "PostOrder -----------------------" << endl;
	PostOrderTree(root);
	cout << endl << "PostOrder -----------------------" << endl;
	PostOrderTreeIterater(root);


	cout << endl << "-----------------------------------------------------------------------------"<<endl;
	cout << endl << "LevelOrder -----------------------" << endl;
	LevelOrderTree(root);
	cout << endl;
	*/

}

void KBigNumTest()
{
	int * array = generateRandomArray(100);
	cout << endl <<  "---------------------Generate Over-------------------"<< endl;

	cout <<  "---------KHeapMaxNum Sort Start---------"<<endl;

    KHeapMaxNum(array, 100, 10);
    cout << endl;

	cout <<  "---------getKBigNum_quicksort Start---------"<<endl;
	getKBigNum_quicksort(array, 100, 10);
	cout << endl;
	cout <<  "---------getKBigNum_partsort Start---------"<<endl;
	getKBigNum_partsort(array, 100, 10);
	cout << endl;
	cout <<  "---------getKBigNum_kthMax Start---------"<<endl;
    getKBigNum_kthMax(array, 100, 10);
    cout << endl;

	delete[] array;
}

    
int tempTest()
{
    int length1 = 4;
    int length2 = 3;

    int **LCS_length;
    LCS_length = (int**)(new int[length1]);
    for(int i = 0; i < length1; ++ i)
        LCS_length[i] = (int*)new int[length2];

    for(int i = 0; i < length1; ++i)
        for(int j = 0; j < length2; ++j)
            LCS_length[i][j] = 1;

    for(int i = 0; i < length1; ++ i)
    {
        for(int j = 0; j < length2; ++ j)
        {
            cout << LCS_length[i][j] << "  ";
        }
        cout << endl;
    }

    return 0;
}

/*
 * 如何动态定义一个二维数组.
 * Typedef new type.
*/
int NewTest()
{
    typedef int*  PINT;

    int length1 = 4;
    int length2 = 3;

    PINT *LCS_length;
    LCS_length = new PINT[length1];
    for(int i = 0; i < length1; ++ i)
        LCS_length[i] = new int[length2];

    for(int i = 0; i < length1; ++i)
        for(int j = 0; j < length2; ++j)
            LCS_length[i][j] = 8;

    for(int i = 0; i < length1; ++ i)
    {
        for(int j = 0; j < length2; ++ j)
        {
            cout << LCS_length[i][j] << "  ";
        }
        cout << endl;
    }

    return 0;
}

/*
 * 如何动态定义一个二维数组.
 * 通过定义一个一维数组来变相的达到二维数组的效果
*/
int RockTest()
{
    int length1 = 4;
    int length2 = 3;

    int * LCS_length = new int[length1 * length2];

    for(int i = 0; i < length1; ++i)
        for(int j = 0; j < length2; ++j)
            LCS_length[i* length1 + j] = 1;

    for(int i = 0; i < length1; ++ i)
    {
        for(int j = 0; j < length2; ++ j)
        {
            cout << LCS_length[i* length1 + j] << "  ";
        }
        cout << endl;
    }

    return 0;
}

void BinarySearchTest()
{
	int array[] = { 1,2,3,4,5,6,7,8 ,9 ,10,11,23,25,35,38,40, 50,60,63,68, 70, 71, 72,
		78,80,89,90,312,532,890,1000, 3252,5333, 6090,7083,8000,9892,10000, 10001};

	int index = BinarySearch(50, array, sizeof(array)/sizeof(int));

	cout <<"The position is " << index << endl;

}

int main()
{ 
	Stack<int> s;
	Stack<float> s1;

	cout << "输出中文字符" << endl;
	BinarySortTreeTest();

    //KBigNumTest();
	/*
	BinarySearchTest();
	string str1="ABCDEFGHLMNOPQRS";  
	string str2="DCGSRQPOM";  

	IsChildString(str1, str2);
	*/
	/*计数排序测试*/
	//CalculateSort();

#if 0
	SortTest();
#endif

#if 0
	const int LEN = 27;
	//int * arrayPtr = new int[LEN];
	int * arrayPtr = generateRandomArray(LEN);
	/*
	for(int i = 0; i < LEN-1; i++)
		arrayPtr[i] = generateRandom();
		*/
	//initData(arrayPtr);

	HeapSort * heap = new HeapSort(arrayPtr, LEN);
	heap -> SortHeap();

	cout <<endl<< "HeapSort Results as bellow:" <<endl;

	heap->Print();
	delete arrayPtr;
#endif
	//TreeSort();
    //LinkOperation();
	//FindWayOut();
	//AllComposite(18);
	/*
    tempTest();
    cout << "-------------------------------------"<< endl;
    NewTest();
    cout << "-------------------------------------"<< endl;
    RockTest();
	*/
	return 0;
}
